use std::{
    cmp::Ordering, collections::BinaryHeap, env, io::{self, stdin}, usize
};

mod palette;
use palette::*;


struct Strategy {
    actions: Vec<((usize, usize), Color)>,
    palette: Palette<Color>,
    n_patch: u32
}

enum Finished {
    Yes,
    NotYet,
    Dead
}

impl Strategy {
    fn new(palette: Palette<char>, size: &PaletteSize) -> Strategy {
        let n_patch = view_simple(&palette, size);
        Strategy {
            actions: Vec::new(),
            palette,
            n_patch
        }
    }

    /// Generate a new `Strategy` from the old one by filling a patch with some color. 
    fn advance(&self, cells: &Vec<(usize, usize)>, c: Color, size: &PaletteSize) -> Strategy {
        let mut actions = self.actions.clone();
        actions.push((cells[0], c));
        let palette = self.palette.paint_patch(cells, c, size);
        let n_patch = view_simple(&palette, size);
        Strategy {
            actions,
            palette,
            n_patch
        }
    }

    /// Check whether we have reached the goal.
    fn is_finished(&self, target_color: Color, size: &PaletteSize) -> Finished {
        if self.n_patch == 1 {
            if self.palette.at((0, 0), size) == target_color {
                Finished::Yes
            } else {
                Finished::Dead
            }
        } else {
            Finished::NotYet
        }
    }
}

impl PartialEq for Strategy {
    fn eq(&self, other: &Self) -> bool {
        self.n_patch == other.n_patch
    }
}

impl Eq for Strategy {}

impl PartialOrd for Strategy {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Strategy {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.n_patch.cmp(&other.n_patch)
    }
}


fn search(palette: Palette<Color>, size: &PaletteSize, target_color: Color, storage_max: usize)
    -> Vec<Vec<((usize, usize), Color)>> {
    let mut last_step: Vec<Strategy> = Vec::new();
    let mut success = false;
    let mut solutions: Vec<Vec<((usize, usize), Color)>> = Vec::new();

    // Initialization
    last_step.push(Strategy::new(palette, size));

    // For each step
    for n_step in 1.. {
        if success || last_step.is_empty() { break; }
        println!("{n_step}, ");
        let mut current_step: BinaryHeap<Strategy> = BinaryHeap::new();

        // For each strategy
        while let Some(ref s@Strategy{ref palette, ..}) = last_step.pop() {
            // For each patch to be paint
            for (cells, neighbors) in  view(&palette, size) {
                // For each color to paint
                for c in neighbors {
                    // Paint the `cells` into color `c`
                    let s_new = s.advance(&cells, c, size);

                    match s_new.is_finished(target_color, size) {
                        Finished::Yes => {
                            success = true;
                            solutions.push(s_new.actions);
                        }
                        Finished::NotYet => {
                            current_step.push(s_new);
                            if current_step.len() > storage_max {
                                current_step.pop();  // Remove the strategy with maximal number of patches
                            }
                        }
                        Finished::Dead => {}
                    }
                }
            }
        }
        last_step = current_step.into_sorted_vec();
        last_step.reverse();  // Descending in n_patches so that we can pop the last one
    }

    solutions
}


fn main() -> io::Result<()> {
    let mut storage_max:usize = 200;  // Default value
    let target_color: Color;
    let (mut h, mut w) = (0usize, 0usize);

    // = Command-line
    if let Some(val) =
        env::args().nth(1)
        .and_then(|val| val.parse::<usize>().ok()) {
        storage_max = if val > 10 { val } else { 10 }
    }

    // = Input
    let mut lines = stdin().lines();
    target_color = lines.next().unwrap().unwrap().chars().next()
        .unwrap_or_else(|| panic!("Unspecified target color"));

    let mut rows: Vec<Vec<Color>> = Vec::new();
    for line in lines {
        let row: Vec<Color> = line.unwrap().chars().collect();
        if row.is_empty() { break }
        if w < row.len() { w = row.len() }
        rows.push(row);
        h += 1;
    }
    if h == 0 { panic!("Empty palette") }

    // = Construct palette
    rows.iter_mut().for_each(|row| row.resize(w, ' '));
    let size = PaletteSize::new_from(h, w);
    let palette: Palette<Color> = Palette::new_from(rows);
    if !palette.contains(&target_color) {
        panic!("Target color not in the palette");
    }

    // = Search
    let solutions = search(palette, &size, target_color, storage_max);

    // = Output
    for sln in solutions {
        // Convert to human-readable indices
        let sln2: Vec<((usize, usize), Color)> =
            sln.iter().map(|((h,w), c)| ((h+1, w+1), *c)).collect();
        println!("{:?}", sln2);
    }

    Ok(())
}
